package main

import "fmt"

func minWindow(s, t string) string {
	if s == "" || t == "" {
		return ""
	}
	left, right := 0, 0
	tWin := make(map[string]int, 0)
	sWin := make(map[string]int, 0)
	result := ""
	valid := 0 //窗口中满足要求的字符串的个数
	start, lens := 0, -1

	for i := 0; i < len(t); i++ {
		tWin[string(t[i])] = 1
	}

	for right < len(s) {
		c := string(s[right]) // 将移入窗口的字符
		right++               // 右移窗口
		// 窗口数据更新

		if tWin[c] > 0 {
			sWin[c]++
			if sWin[c] == tWin[c] {
				valid++
			}
		}

		// 判断左侧窗口是否需要收缩
		for valid == len(tWin) {
			// 更新最小覆盖子串
			if right-left < lens {
				start = left
				lens = right - left
			}
			d := string(s[left]) //移除窗口的字符串
			left++               //左移窗口
			if tWin[d] > 0 {
				if tWin[d] == sWin[d] {
					valid--
				}
				sWin[d]--
			}
		}
	}

	if lens != -1 {
		result = s[start:lens]
	}
	return result

}

func main() {
	fmt.Println(minWindow("ADOBECODEBANC", "ABC"))
	// fmt.Println("000000")
	// fmt.Println(minWindow("a", "a"))
	// fmt.Println(minWindow("a", "aa"))

	// fmt.Println(minWindow2("ADOBECODEBANC", "ABC"))
	// fmt.Println("000000")
	// fmt.Println(minWindow2("a", "a"))
	// fmt.Println(minWindow2("a", "aa"))
}

func minWindow2(s string, t string) string {
	if s == "" || t == "" {
		return ""
	}
	var tFreq, sFreq [256]int
	result, left, right, finalLeft, finalRight, minW, count := "", 0, -1, -1, -1, len(s)+1, 0

	for i := 0; i < len(t); i++ {
		tFreq[t[i]-'a']++
	}

	for left < len(s) {
		if right+1 < len(s) && count < len(t) {
			sFreq[s[right+1]-'a']++
			if sFreq[s[right+1]-'a'] <= tFreq[s[right+1]-'a'] {
				count++
			}
			right++
		} else {
			if right-left+1 < minW && count == len(t) {
				minW = right - left + 1
				finalLeft = left
				finalRight = right
			}
			if sFreq[s[left]-'a'] == tFreq[s[left]-'a'] {
				count--
			}
			sFreq[s[left]-'a']--
			left++
		}
	}
	if finalLeft != -1 {
		result = string(s[finalLeft : finalRight+1])
	}
	return result
}
